package com.ting.test.algorithms.图;

public class 将一个数组表示的图转换为我们定义的图 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{};
        Graph graph = parse(arr);
    }

    /**
     * 该二维数组的结果为[[3,5,9],[0,2,4]}
     * 其中
     * arr[i]表示图中的某一条边
     * arr[i][0]表示该边的标签/权重
     * arr[i][1]表示该边的开始节点
     * arr[i][2]表示该边的结束节点
     *
     * @param arr
     * @return
     */
    private static Graph parse(int[][] arr) {
        Graph graph = new Graph();
        if (arr == null) {
            return graph;
        }

        for (int i = 0; i < arr.length; i++) {
            int[] temp = arr[i];//边
            int weight = temp[0];//边的权重
            int from = temp[1];//边的起点
            int to = temp[2];//边的终点
            // 先判断图中有没有这个节点，如果没有 则添加
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            // 先判断图中有没有这个节点，如果没有 则添加
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }

            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            fromNode.out = fromNode.out + 1;//from节点的出度+1
            toNode.in = toNode.in + 1;//to节点的入度—+1
            fromNode.nexts.add(toNode);//from节点的直接相邻节点+1
            Edge edge = new Edge(weight, fromNode, toNode);
            graph.edges.add(edge);//
            fromNode.edges.add(edge);//form节点的直接相邻边+1
        }

        return graph;
    }
}
